In many different applications, the processes of modeling, design, and analysis often involve the simultaneous treatment of objects or artifacts (i.e., parts designed by humans) or anatomical structures. However, such objects can be represented in alternative ways. An inherent conflict arises in these different aspects of the problem because the geometric descriptions are completely different for these different approaches in representing objects. For example, artifact descriptions are typically produced as the output of computer-aided design (CAD) software and consist of a collection of parametric patches that comprise the boundary of the artifact. In contrast, the native description of an anatomical object or other scanned structure typically consists of an image stack produced using computed tomography (CT) or magnetic resonance imaging (MRI) in which the structure is evident as a result of the different intensities within regions of images in the image stack. The conventional approach for simultaneously dealing with both categories of entities involves working primarily in the world of CAD. The scanner data must be processed to determine segmentation (i.e., to decide which voxel in the scanner data belongs to each object of interest). The segmented results are then converted to traditional boundary representation (b-rep) CAD models. However, a CAD model can include such large numbers of parametric patches such as triangles (often on the order of 106 or 107 in number) that performing standard CAD operations on the model becomes problematic. Most traditional CAD systems are designed to deal with environments composed of at most, thousands of individual objects with tens of thousands of individual surfaces. Beyond these limits, the performance of many CAD systems is unacceptably slow. These concerns suggest that forcing the disparate aspects of this problem into a traditional CAD environment may not really be the best approach. While the CAD environment is acceptable for creating models of limited complexity, as the complexity of models increases, the CAD environment will become increasingly inefficient for this purpose. For example, the complexity of many anatomical structures will likely require that a different novel approach be developed for creating appropriate models that does not rely on the CAD environment. Thus, a desirable alternative approach might be to create a solid model from the volumetric image scanning data using a novel computationally efficient process.
There are many applications that might benefit from an efficient method of converting the data produced by volumetric scans of one or more objects or artifacts into solid models. However, a particular application, such as artificial joint replacement, merits special attention in this regard, because the benefits that might accrue from the use of such a method clearly justify further research in this area. According to the Healthcare Cost and Utilization Project that is operated by the U.S. Department of Heath and Human Services Agency for Healthcare Research and Quality, each year, more than 750,000 hip and knee replacement surgeries are performed at a cost that, by 2005, had already grown to almost 32 billion dollars. A significant fraction of the patients (i.e., 14% of knee replacement patients) must return for a second operation and adjustment procedure to modify their implants, at an annual total cost of about five billion dollars. This rate of unsuccessful first-time procedures is not a reflection of a lack of skilled surgeons, but is instead more the result of limitations of implant fit and placement. Significant amounts of healthcare money and patient discomfort could be saved if implants (and implant placement procedure plans) could be customized to each specific patient. And, as noted above, there are many non-medical applications for a technique that can use scan data to produce solid models. The solid models can then be employed in fabricating various types of objects, properly positioning objects relative to each other, and/or achieving a good fit between two or more objects that are coupled together.
Conventional solid modeling software typically employs boundary representations (b-reps) as the dominant paradigm, but there are cases in which b-rep models may not be the most efficient or effective format for this purpose. For example, models can be derived from voxelized intensity data obtained from various types of three-dimensional (3-D) scanners, such as those used for CT, MRI, and positron emission tomography (PET), using segmentation, i.e., determining the voxels in the scan data that belong to a specified object or structure. A number of different segmentation algorithms are available. While the segmented voxel set associated with an object provides a spatial decomposition model of a scanned object, the modeling range is limited to objects having boundaries that coincide with voxel boundaries. In particular, objects with curved surfaces cannot be accurately represented using this approach. Since many objects of interest, such as anatomical objects, have curved surfaces, an alternative to the b-rep solid modeling of objects is needed.
Attempts at improving the approximation of objects with curved surfaces typically involve polygonization of isosurfaces of associated scalar functions, including occupancy functions or signed distance functions (SDFs). Polygonized models span a broad modeling range, but they cannot faithfully represent objects with curved surfaces. Also, attempts at achieving an accurate approximation of curved surfaces can produce data having undesirably large file sizes. One conventional approach to producing models with smooth surfaces involves employing the segmentation results slice-by-slice, to produce surface curves that can be interpolated by splines, which are then lofted to produce smooth surfaces. Such an approach can be useful, but encounters complications when the number of connected components changes between slices. Accordingly, existing methods do not yet achieve a desired level of effectiveness.
However, it may be useful to follow the lead provided by polygonization methods. Specifically, it may be useful to invoke the existence of underlying scalar functions. Polygonization methods strongly suggest the usefulness of implicit or function-based representations (f-reps). Yet, this approach is still relatively computationally intensive and does not provide the resolution that may be desired for creating solid models of some objects or artifacts.
With some human intervention, modern segmentation algorithms can convert the intensity data produced by volumetric scans to signed distance data that specifies the distance from the center of each voxel in the scan data to a boundary of an object being segmented. In this approach, a negative sign indicates an interior voxel within the object, and a positive sign an exterior voxel that is in the volume outside the object. Earlier work in this area has shown the advantage of using a graph cuts method to initially identify the voxels comprising scanner data that are part of an object or part of the background, i.e., to determine which points are inside an object and which are outside, and then using a level sets method to refine the voxel identification. The level sets method determines the SDF values that define a model of the object.
In the approach discussed above, the points labeled as inside and outside an object are retained. Wavelets (such as Daubechies wavelets) can be employed to interpolate known SDF values at the voxel centers in the scanned data to produce wavelet-SDF-rep models in which the wavelet interpolant provides the function that represents the segmented object. Since there are many possible choices of wavelets (even restricting the choices to Daubechies wavelets, since the genus of Daubechies wavelets can still be chosen), a grid of signed distance values does not uniquely determine the object, because the interpolant is not, in general, uniquely determined away from the voxel centers. However, even using the wavelet approach, the resolution and efficiency of the method are not as good as might be needed for producing high quality models of an object such as an anatomical skeletal component.
Accordingly, it would be desirable to develop a method for using the range of SDFs (and the associated range of implicit object geometries) associated with a uniform grid of specified sample values, like those derived from voxel data. This approach might be used to create interval extensions of the signed distance so that all SDFs associated with the sampling lie within the bounds of an interval extension. The interval extensions of SDFs should be usable in one, two, three, or more dimensions.